This invention relates to an apparatus and method for recognizing various kinds of patterns including characteristic patterns, and particularly to an apparatus and method which allow accurate recognition of input patterns which are subject to overall changes.
Pattern recognition apparatus have recently begun to be practically used as inputs to computer systems. The conventional pattern recognition methods are classified as a pattern matching method and a character extraction method. The similarity method, one of the pattern matching methods, has been widely utilized. In this method, the simple similarity S is expressed by the following equation, ##EQU1## where
f is an n-dimensional vector indicating an unknown black and white pattern on a plane;
f.sub.o is an n-dimensional vector indicating a standard reference pattern to which the pattern f is referred;
(f, f.sub.o) is the scalar (dot) product of the vectors f and f.sub.o ; and
.parallel.f.parallel. and .parallel.f.sub.o .parallel. are norms (magnitudes) of the vectors f and f.sub.o, respectively.
More specifically, any pattern drawn on a plane can be expressed by an n-dimensional vector in the following manner: The plane is divided into n picture elements or cells, each of which has a darkness or density which is a function of its position on the plane. If the positions of the picture elements are expressed as x.sub.1, x.sub.2, . . . , x.sub.n and the darkness of the picture elements are expressed as f(x.sub.1), f(x.sub.2), . . . , f(x.sub.n), respectively, the vector f can be uniquely defined in n-dimensional coordinates where f(x.sub.1), f(x.sub.2), . . . , f(x.sub.n) correspond to the projections of the vector f on the coordinate axes 1, 2, . . . , n.
The simple similarity defined by equation (1) means that S takes maximum value 1 when two vectors f and f.sub.o in n-dimensional coordinates are parallel and that S takes minimum value 0 when the two vectors are perpendicular. Thus S varies from the value 1 where two patterns on the plane are overlapped to the value 0 where the two patterns are quite different from each other.
This simple similarity method has a great advantage that the design of a dictionary of standard reference patterns can be automated, and that it is not greatly affected by such local noise as stains or scratches in the patterns. It is liable to be affected adversely, however, by such overall changes in the patterns as occur in handwritten letters or voice sound patterns.
One conventional method that has been developed and used to overcome these drawbacks is the multiple similarity method shown, for example, in U.S. Pat. No. 3,688,267. According to this method, a number of secondary reference patterns are provided, for each one of the primary reference patterns, each of which corresponds to a deformation of the primary reference pattern. Multiple similarity S is expressed as follows: ##EQU2## where .phi..sub.m (m=1, 2, . . . M) are the primary and secondary reference patterns. This value of S also varies from 0 to 1 in accordance with the similarity between the pattern f and the set of reference patterns .phi..sub.m. While this multiple similarity method is useful for the recognition of patterns which are subject to overall deformations, there still existed the problem that much labor for gathering sample data, and highly complicated computation, were needed in the design of the dictionary.
One example of the conventional character extraction method is shown in U.S. Pat. No. 4,541,511. In this method, various kinds of characters are extracted from various parts of the patterns, and the reference patterns and unknown patterns are recognized by a combination of these reference characteristic patterns. The problem in this method, however, has been that complicated algorithmic processing is required. There is also the difficulty that the method cannot be easily automated and much labor is needed to operate it.
It has also been proposed that the multiple similarity method and the character extraction method be combined for more accurate recognition of handwritten letters. This method is disclosed, for example, in the preliminary report for the National Convention of the Electrocommunication Society, page 5-378, published by the Japan Electrocommunication Society. According to this method, the multiple similarity method is applied to the unknown patterns in the first stage, and in the second stage the character extraction method is applied to the result from the first stage. This combined method is useful for the recognition of complicated handwritten letters such as Japanese letters. The apparatus for realizing the method is, however, complicated; and automatic design of the dictionary is also difficult.